Background: Enteroaggregative Haemorrhagic E. coli (EAHEC) is a new pathogenic group of E. coli characterized by the presence of a vtx2-phage integrated in the genomic backbone of Enteroaggregative E. coli (EAggEC). So far, four distinct EAHEC serotypes have been described that caused, beside the large outbreak of infection occurred in Germany in 2011, a small outbreak and six sporadic cases of HUS in the time span 1992–2012. In the present work we determined the whole genome sequence of the vtx2-phage, termed Phi-191, present in the first described EAHEC O111:H2 isolated in France in 1992 and compared it with those of the vtx-phages whose sequences were available. Results: The whole genome sequence of the Phi-191 phage was identical to that of the vtx2-phage P13374 present in the EAHEC O104:H4 strain isolated during the German outbreak 20 years later. Moreover, it was also almost identical to those of the other vtx2-phages of EAHEC O104:H4 strains described so far. Conversely, the Phi-191 phage appeared to be different from the vtx2-phage carried by the EAHEC O111:H21 isolated in the Northern Ireland in 2012.The comparison of the vtx2-phages sequences from EAHEC strains with those from the vtx-phages of typical Verocytotoxin-producing E. coli strains showed the presence of a 900 bp sequence uniquely associated with EAHEC phages and encoding a tail fiber. Conclusions: At least two different vtx2-phages, both characterized by the presence of a peculiar tail fiber-coding gene, intervened in the emergence of EAHEC. The finding of an identical vtx2-phage in two EAggEC strains isolated after 20 years in spite of the high variability described for vtx-phages is unexpected and suggests that such vtx2-phages are kept under a strong selective pressure.The observation that different EAHEC infections have been traced back to countries where EAggEC infections are endemic and the treatment of human sewage is often ineffective suggests that such countries may represent the cradle for the emergence of the EAHEC pathotype. In these regions, EAggEC of human origin can extensively contaminate the environment where they can meet free vtx-phages likely spread by ruminants excreta. Electronic supplementary material: The online version of this article (doi:10.1186/1471-2164-15-574) contains supplementary material, which is available to authorized users.